package com.note.feng.dataStructureAlgorithm;

/**
 * 基本概念
 * 1、数据结构(data structure)
 * 		数据结构是相互之间存在一种或多种特定关系的数据元素的集合
 * 		研究的是数据的逻辑结构和数据的物理结构以及他们之间的相互关系
 * 		数据结构包括：线性结构和非线性结构
 * 2、算法(Algorithm)
 * 		是解题方案的准确而完整的描述，是一系列解决问题的清晰指令
 * 		算法代表着用系统的方法描述解决问题的策略机制
 * 3、度量算法的执行时间
 * 		度量一个程序(算法)执行时间的两种方法
 * 			事后统计法
 * 			事前估算法
 * 		统计某个算法的时间复杂度来度量方法的优越性
 * 		时间复杂度统计法属于事前估算法
 * 4、时间频度T(n)
 * 		时间频度：一个算法花费的时间与算法中语句的执行次数成正比
 * 		一个算法中的语句执行次数称之为语句频度或时间频度，记为T(n)，n称为问题的规模
 * 5、时间复杂度O(n)
 * 		某个函数(n)，使得当n趋近与无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n) = O(f(n))
 * 		T(n)不同，但时间复杂度可能相同
 * 		称O(f(n))为算法的渐进时间复杂度，简称时间复杂度
 * 6、最坏时间复杂度
 * 		最坏情况下的时间复杂度称最坏时间复杂度
 * 		一般讨论的时间复杂度均是最坏情况下的时间复杂度
 * 		最坏情况调的时间复杂度是算法在任何输入实例上运行时间的界限
 * 7、平均时间复杂度
 * 		平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，改算法的运行时间
 * 8、空间复杂度
 * 		一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，他也是问题规模n的函数
 * 		空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度
 * 		在做算法分析时，主要讨论的是时间复杂度
 * 		从用户体验上看，更看重的是程序的执行的速度
 * 		一些缓存产品(redis、memcache)和算法(基数排序)本质就是用空间换时间
 * 9、计算时间复杂度原则
 * 		1、忽略常数项
 * 		2、忽略低次项
 * 		3、忽略系数
 * 		4、计算时间频度
 * 		5、常见的时间复杂度
 * 			常数阶O(1)
 * 			对数阶O(log₂n)
 * 			线性阶O(n)
 * 			线性对数阶O(nlog₂n)
 * 			平方阶O(n^2)
 * 			立方阶O(n^3)
 * 			k次方阶O(n^k)
 * 			指数阶O(2^n)
 * 			时间复杂度有小到大依次为：O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n^k) < O(2ⁿ)
 * @author Administrator
 *
 */
public class basicConcept {
	
	public static void main(String [] args) {
		//分析：1+2+3......+100，两种算法的时间频度
		//算法一
		int sum = 0;
		int start = 1;
		int end = 100;
		for(int i = start; i <= end; i++) {
			sum += i;
		}
		//算法二
		sum = (start + end) * end / 2;
		
		/**
		 * 常数阶O(1)
		 * 无论代码执行了多少行，只要是没有循环等复杂结构，那这段代码的时间复杂度就都是O(1)
		 */
		int i = 1;
		int j = 100;
		i ++;
		j ++;
		int k = i * j;
		
		/**
		 * 对数阶O(log₂n)
		 * 如果 N = a^x (a > 0, 且a ≠ 1 )，那么数x叫做以a为底的对数，记作 x = log₂n
		 * a叫做对数的底数，N叫做真数，x叫做"以a为底N的对数"
		 */
		int a = 1;
		int n = 100;
		while(a < n) {
			a = a * 2;
		}
		
		/**
		 * 线性阶O(n)
		 * for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的
		 */
//		int j = 0,n = 100;
//		for(int i = 1; i < n; i++) {
//			j = i;
//			j ++;
//		}
		
		/**
		 * 线性对数阶O(nlog₂n)
		 * 将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logn)，也就是O(logn)
		 * 底数没写，默认为2(logn = log₂n)
		 */
//		int i = 0,n = 100;
//		for(int m = 1; m < n; m ++) {
//			i = 1;
//			while(i < n) {
//				i = i * 2;
//			}
//		}
		
		/**
		 * 平方阶O(n^2)
		 * 如果把O(n)的代码再嵌套循环一遍，它的时间复杂度就是O(n^2)
		 */
//		int i = 1,j = 0,n = 100,res = 0;
//		for(i = 1; j < n; i ++) {
//			for(j = 0;j < n;j ++) {
//				res = i;
//				res ++;
//			}
//		}
		
		/**
		 * 立方阶O(n^3)  k次方阶O(n^k)
		 * 立方阶相当于3层嵌套循环，k次方阶相当于k层循环
		 */


    }

}
